package jjn.acwing.algorithm_basic.chapter1.math;

import java.util.Scanner;

/**
 * @author Jjn
 * @since 2023-09-14 08:59
 */
public class Acwing867 {
    
    static void divide(int num) {
        for (int i = 2; i <= num / i; i++) {
            if (num % i == 0) {
                int s = 0;
                while (num % i == 0) {
                    num = num / i;
                    s++;
                }
                System.out.printf("%d %d\n", i, s);
            }
        }
        if (num > 1) {
            System.out.printf("%d %d\n", num, 1);
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        while (n-- > 0) {
            int num = scanner.nextInt();
            divide(num);
        }
    }
}
